package com.suxin.algorithm.linked;

/**
 * @author Tang
 * @classname DoubleLinked
 * @description [ 双链表 ]
 * @date 2022/3/29 22:31
 */
public class DoubleLinked<T> {

    private Node head;

    private int size;

    /**
     * 添加头结点
     * @param t
     */
    public void addHead(T t) {
        if (head == null) {
            head = new Node(t, head, null);
        } else {
            Node node = new Node(t, head, null);
            head.pre = node;
            head = node;
        }
        this.size++;
    }

    /**
     * 添加尾结点
     * @param t
     */
    public void addTail(T t) {
        addPosition(t, this.size);
    }

    /**
     * 前插入法,,后插入法需要考虑是末节点的情况
     * @param t
     * @param index
     */
    public void addPosition(T t, int index) {
        if (index > this.size) {
            throw new IllegalArgumentException("index out!");
        }
        // 头插入
        if (index == 1) {
            addHead(t);
        }
        // 其他位置的前插入法
        Node temp = this.head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        Node node = new Node(t);

        Node cur = temp.pre;
        // 新节点的下一个节点是当前节点
        node.next = temp;
        // 当前节点的前驱节点是新节点
        temp.pre = node;
        // 当前节点的前驱节点的next是新节点
        cur.next = node;
        // 新节点的前驱节点是 当前节点的前驱节点
        node.pre = cur;

        this.size++;
    }

    public void addEle(T t, T des) {
        // 虚拟节点方便插入
        Node dummy = new Node(null, this.head, null);
        Node temp = dummy;
        while (dummy != null) {
            // 前插入法
            if (t.equals(dummy.data)) {
                Node node = new Node(t);
                Node cur = dummy.pre;
                // 新节点的下一个节点是当前节点
                node.next = dummy;
                // 当前节点的前驱节点是新节点
                dummy.pre = node;
                // 当前节点的前驱节点的next是新节点
                cur.next = node;
                // 新节点的前驱节点是 当前节点的前驱节点
                node.pre = cur;
                this.size++;
            }
            dummy = dummy.next;
        }
        this.head = temp.next;
    }

    public void removeEle(T t) {
        Node dummy = new Node(t, this.head, null);
        Node cur = dummy;
        while (dummy.next != null) {
            if (t.equals(dummy.data)) {
                // 当前节点的下一个下一个节点的前驱节点 为当前节点
                dummy.next.next.pre = dummy;
                // 当前节点的后续节点为 下一个下一个的节点
                dummy.next = dummy.next.next;
            }
        }
        this.head = cur.next;
        this.head.pre = null;
    }

    /**
     * 移除第一个
     * @return
     */
    public T removeFirst() {
        Node cur = this.head;
        T data = (T) cur.data;
        this.size--;
        if (this.size == 1) {
            this.head = null;
            return data;
        }
        this.head = this.head.next;
        this.head.pre = null;
        return (T) cur.data;
    }

    /**
     * 删除最后一个
     * @return
     */
    public T removeLast() {
        Node temp = this.head;
        for (int i = 0; i < this.size - 1; i++) {
            temp = temp.next;
        }
        temp.pre.next = null;
        temp.pre = null;
        this.size--;
        return (T) temp.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node cur = this.head;
        while (cur != null) {
            sb.append(cur.data).append("-->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        DoubleLinked doubleLinked = new DoubleLinked();
        doubleLinked.addHead("1");
        doubleLinked.addHead("2");
        doubleLinked.addTail("3");
        doubleLinked.addEle("1",2);

        System.out.println(doubleLinked);
        doubleLinked.removeFirst();
        System.out.println("删除头结点--->" + doubleLinked);

        doubleLinked.removeLast();
        System.out.println("删除尾结点--->" + doubleLinked);
    }


    private static class Node<T> {

        private T data;

        private Node next;

        private Node pre;

        public Node(T data, Node next, Node pre) {
            this.data = data;
            this.next = next;
            this.pre = pre;
        }

        public Node(T data) {
            this.data = data;
            this.next = null;
            this.pre = null;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public Node getPre() {
            return pre;
        }

        public void setPre(Node pre) {
            this.pre = pre;
        }
    }

}